function solveNQueens(n) {
    const solutions = [];
    const queens = Array(n).fill(-1);
    const columns = new Set();
    const diagonal1 = new Set();
    const diagonal2 = new Set();
    
    // 生成棋盘字符串表示
    function generateBoard() {
        const board = [];
        for (let i = 0; i < n; i++) {
            const row = Array(n).fill('.');
            row[queens[i]] = 'Q';
            board.push(row.join(''));
        }
        return board;
    }
    
    // 回溯函数
    function backtrack(row) {
        if (row === n) {
            const board = generateBoard();
            solutions.push(board);
        } else {
            for (let i = 0; i < n; i++) {
                const diag1 = row - i;
                const diag2 = row + i;
                
                // 检查列和对角线是否冲突
                if (columns.has(i) || diagonal1.has(diag1) || diagonal2.has(diag2)) {
                    continue;
                }
                
                // 放置皇后
                queens[row] = i;
                columns.add(i);
                diagonal1.add(diag1);
                diagonal2.add(diag2);
                
                // 递归处理下一行
                backtrack(row + 1);
                
                // 回溯操作
                columns.delete(i);
                diagonal1.delete(diag1);
                diagonal2.delete(diag2);
            }
        }
    }
    
    backtrack(0);
    return solutions;
}

// 测试代码
const t1 = performance.now();
const solutionsArray = [];
for (let i = 0; i < 15; i++) {
    const solutionsText = solveNQueens(i);
    solutionsArray.push(solutionsText.length);
}
console.log(solutionsArray[solutionsArray.length - 1]);
console.log(performance.now() - t1);